package leetcode.problems.P84柱状图中最大的矩形;

import java.util.Stack;

public class LargestRectangleArea {
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if (n == 0) return 0;
        int[] left = new int[n], right = new int[n];// 计算以当前下标为准，能够往左、右扩散的最大连续区间长度
        Stack<int[]> stack = new Stack<>();
        for (int i = 0; i < n; i++) {// 计算当前矩形能往左扩展的最长距离
            // heights[i]比栈顶大就进栈，否则一直出栈
            while (!stack.isEmpty() && stack.peek()[1] >= heights[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? 0 : stack.peek()[0] + 1;// 如果为0表示当前元素在[0, i]区间内是最小的，向左可以扩散i个单位
            stack.push(new int[]{i, heights[i]});
        }
        stack.clear();
        for (int i = n - 1; i >= 0; i--) { // 计算当前矩形能往右扩展的最长距离
            // heights[i]比栈顶大就进栈，否则一直出栈
            while (!stack.isEmpty() && stack.peek()[1] >= heights[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n - 1 : stack.peek()[0] - 1;// 如果为0表示当前元素在[i,n-1]区间内是最小的，向右可以扩散n-i个单位
            stack.push(new int[]{i, heights[i]});
        }
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] + 1));
        }
        return maxArea;
    }
}